\chapter{数据结构}
\thispagestyle{empty}

\setlength{\fboxrule}{0pt}\setlength{\fboxsep}{0cm}
\noindent\shadowbox{
\begin{tcolorbox}[arc=0mm,colback=lightblue,colframe=darkblue,title=Data Structure]
\kai{~~~~数据结构是计院三大核心课之一，在设计离散类型算法时，决定数据结构通常是第一步。}\\

\kai{~~~~学习和设计数据结构时，需要掌握数据结构两大核心: 逻辑结构和存储结构。前者定义了数据间的关系和需要的数据操作，即确定抽象数据类型ADT； 后者决定数据在程序中的存储方式和具体实现，一般就分顺序和链表两种。
在此基础上，需要掌握数据结构对应的典型应用，也就是由数据结构派生出的算法。}\\

\kai{~~~~数据结构的内容: 线性表，栈，队列，字符串，树，二叉树，图，查找技术。}\\


\end{tcolorbox}}
\setlength{\fboxrule}{1pt}\setlength{\fboxsep}{4pt}


\newpage

\section{数据结构基本概念}

\subsection{数据结构}

\textbf{1. 定义: }非数值问题的数据组织和处理。

\textbf{2. 包含内容: }逻辑结构，存储结构，算法，数据处理技术。

\textbf{3. 逻辑结构: }描述数据间的关联关系。常见的有集合，线性结构，树形结构和图结构。

\textbf{4. 存储结构: }描述数据在计算机内的存储方式，分为顺序和链表两种。

\textbf{5. 数据操作: }即数据的增加，删除，修改，查找，排序等

\textbf{6. 抽象数据类型(ADT): }数据结构以及定义在其上的数据操作的总称。确定数据的逻辑结构和操作后可设计ADT，确定存储结构后可具体实现ADT。

\subsection{面向对象程序设计}

\textbf{1. 类: }计算机用于创建对象的模板，含有属性，方法和事件等。

\textbf{2. 封装: }将数据成员与方法嵌入类中，外部无法访问私有成员，只能访问类的给定接口以实现对应功能。

\textbf{3. 声明: }类需要声明数据类型，成员变量，成员函数与成员权限，不占用存储空间； 声明对象即将类实例化，可用"。" 访问对象公有成员。

\textbf{4. 构造函数: }声明对象时首先调用的函数，作初始化工作。

\textbf{5. 析构函数: }对象被释放时调用的函数，作清理工作。

\textbf{6. C++的动态内存分配: }new 申请分配内存，并返回指向该内存的指针； delete释放指针指向的内存，指针本身不被删除。

\textbf{7. 模板: }template<typename T>，使变量或函数可取任意预设类型。

\textbf{8. 参数传递: }有传值，传指针(*)，传引用(\&)三种. 传值改形参时实参不变，后两种改形参时实参跟着改变。

\section{线性表}

\subsection{逻辑结构}

\textbf{1. 定义: }$n$个具有相同数据类型的元素构成的序列，$n$称为线性表的长度。

\textbf{2. C++中的STL: }vector。

\begin{lstlisting}[language=C++]
    #include<vector>
\end{lstlisting}

\textbf{3. 数据操作: }
\begin{lstlisting}[language=C++]
    vector<int> V; //定义与初始化
    V.push_back(int); //在线性表末尾增加元素
    V.insert(int p, int); //在第p个位置插入元素
    V.pop_back(); //删除线性表末尾的元素
    V.erase(int p); //删除第p个位置的元素
    V.clear(); // 清空线性表
    V.size(); // 查询线性表元素个数
    V.begin(); //线性表首元素位置
    V.end(); // 线性表末尾元素位置
    V[p]; //访问线性表第p个位置的元素，也可V.at(int p); 
    V.empty(); //判断线性表是否为空
\end{lstlisting}
    
\textbf{4. 抽象数据类型定义: }

~~~~ (1) private: 数据主体，线性表长度；

~~~~ (2) public: 提供数据增删改查，求长度，判断是否为空的接口

\subsection{存储结构}

\textbf{1. 顺序表: }静态存储结构。数据主体用数组存储，适用于事先知道最大长度的情形。

\textbf{2. 链表: }动态存储结构。用结点存储单元素及其后继元素指针，插入与删除很方便。定义如下: 
\begin{lstlisting}[language=C++]
    struct node
    {
        int x;      //数据主体
        node *p;    //指向后继结点
    };
\end{lstlisting}

\section{栈}

\subsection{逻辑结构}

\textbf{1. 定义: }仅在顶端插入与删除元素的线性表。越先进栈的元素越后出栈，称为FILO。

\textbf{2. C++中的STL: }stack。

\begin{lstlisting}[language=C++]
    #include<stack>
\end{lstlisting}

\textbf{3. 数据操作: }

\begin{lstlisting}[language=C++]
    stack<int> S; //定义与初始化
    S.push(int); //在栈顶插入元素
    S.top(); //查询栈顶元素
    S.pop(); //弹出栈顶元素
    S.size(); //查询栈内元素个数
    S.empty(); //判断栈是否为空
\end{lstlisting}

\textbf{4. 抽象数据类型定义: }

(1) private: 数据主体，栈的长度；

(2) public: 提供数据的插入和删除，查询栈顶元素，求长度，判断是否为空的接口。

\subsection{存储结构}

\textbf{1. 顺序栈: }同顺序表，在此基础上仅支持栈顶元素的插入与删除。

\textbf{2. 链栈: }同链表，在此基础上仅支持栈顶的插入与删除。

\subsection{算法与应用}

\textbf{1. 表达式求值: }所有的计算按照从左到右的顺序执行。用两个栈分别存储操作数和运算符: 

(1) 遇到操作数: 压入操作数栈；

(2) 遇到运算符: 若优先级比运算符栈顶元素低，则将操作数栈的两个顶端元素弹出并根据运算符栈顶元素运算，将运算结果压入操作数栈； 否则压入运算符栈。

\textbf{2. 深度优先搜索: }以栈的形式存储搜索顺序。搜索某一步时，依次选择下一步方案并压入栈； 当前步结束后，将其从栈顶弹出。

\section{队列}

\subsection{逻辑结构}

\textbf{1. 定义: }仅允许一端插入另一端删除的线性表。越先进栈的元素越先出栈，称为FIFO。

\textbf{2. C++中的STL: }queue。

\begin{lstlisting}[language=C++]
    #include<queue>
\end{lstlisting}

\textbf{3. 数据操作: }

\begin{lstlisting}[language=C++]
    queue<int> Q;  //定义与初始化
    Q.push(int);  //队列头部插入元素
    Q.front();  //查询队列头部元素
    Q.back();  //查询队列尾部元素
    Q.pop();  //弹出队列头部元素
    Q.size();  // 查询队列元素个数
    Q.empty();  //判断队列是否为空
\end{lstlisting}

\textbf{4. 抽象数据类型定义: }

(1) private: 数据主体，队列的长度；

(2) public: 提供数据的插入和删除，查询队列头部/尾部，求长度，判断是否为空的接口。

\subsection{存储结构}

\textbf{1. 顺序队列: }同顺序表，在此基础上仅支持队尾插入，队头删除。

\textbf{2. 链队列: }同链表，在此基础上仅支持队尾插入，队头删除。

\subsection{算法与应用}

\textbf{1. 广度优先搜索: }以队列的形式存储搜索顺序。搜索某一步时, 将所有可能的下一步方案入队； 当前步结束后，将其从队列头部弹出。

\textbf{2. 优先队列: }在队列中按照某种优先级顺序出队，可用大根堆或二叉搜索树维护。C++中的STL为priority\_queue，头文件和队列一致。

\section{字符串}

\subsection{逻辑结构}

\textbf{1. 定义: }零个或多个字符组成的有限序列。

\textbf{2. C++中的STL: }string。
\begin{lstlisting}[language=C++]
    #include<string>
\end{lstlisting}

\textbf{3. 数据操作: }由于字符串和vector<char>没啥区别，因此支持的主要操作也没啥区别。

\begin{lstlisting}[language=C++]
    string s;  //定义并初始化
    s.push_back(char);  //在字符串末尾增加字符
    s.insert(int p,char);  //在第p个位置插入字符
    s.pop_back();  //删除字符串末尾的元素
    s.erase(int p);  //删除第p个位置的元素
    s.clear();  // 清空字符串
    s.size();  // 查询字符个数
    s.find(char);  //查找字符并返回其位置
    s.substr(int n, int l);  // 返回从第n位开始长度为l的字串
    s.begin();  //字符串首元素位置
    s.end();  // 字符串末尾元素位置
    s[p];  //访问字符串第p个位置的元素，也可s.at(int p); 
    s.empty();  //判断字符串是否为空
\end{lstlisting}

\textbf{4. 抽象数据类型: }

~~~~ (1) private: 字符串主体，字符串长度；

~~~~ (2) public: 提供字符增删改查，求长度，判断是否为空的接口

P. S. 字符串通常采用顺序存储，故不讨论其存储结构。

\subsection{算法与应用}

\textbf{1. KMP模式匹配算法: }应用于在字符串T中匹配模式子串S。

~~~~ (1) 计算模式串的next数组: 令next[j] = k，其中k为使得 T[0]$\sim$T[k - 1] = S[j - k]$\sim$S[j - 1] 的最大值。

~~~~ (2) 正常匹配: 逐一检查是否有 S[i] = T[j]。

~~~~ (3) 回退: 若某一位 S[i] != T[j]，则i不动，j回退至next[j]，继续匹配。

\section{树}

\subsection{逻辑结构}

\textbf{1. 定义: }$n$个结点的集合。仅能有一个根节点(最上层)，以此基础上产生由上层到下层的一对多映射，除根结点外的所有点称为子结点。

\textbf{2. 结点的度: }结点拥有的子结点个数。所有结点度的最大值称为这棵树的度。

\textbf{3. 路径: }n$_1\rightarrow$n$_2\cdots \rightarrow$n$_\text{k}$。其中n\_i是n$_{\text{i}-1}$的子节点。

\textbf{4. 数据操作: }前序遍历，中序遍历，后序遍历和层序遍历。

~~~~ (1) 前序遍历: 先根序遍历。遍历顺序为根-其它结点。

~~~~ (3) 后序遍历: 后根序遍历。遍历顺序为其它结点-根。

~~~~ (4) 层序遍历: 从上到下遍历层，每一层按从左到右的顺序遍历结点。

\subsection{存储结构}

\textbf{1. 双亲表示法: }用一维数组存储树中各个结点的数据信息，以及结点的父亲在数组中的下标。利用了子结点只能有一个父亲的特性。

\textbf{2. 孩子表示法: }用一维数组存储树中各个结点的数据信息，并以挂链表的形式存储结点的孩子在数组中的下标。

\textbf{3. 孩子兄弟表示法:} 在多叉树中, 每个结点用二叉链表存储, 左指针指向第一个孩子, 右指针指向右边第一个兄弟. 可借助此表示方法, 将m叉树转化为二叉树.

\section{二叉树}

\subsection{逻辑结构}

\textbf{1. 定义: }二叉树是特殊的树形结构，每个结点顶多有两个子结点，即左儿子与右儿子。

\textbf{2. 满二叉树: }除叶子结点外，其它结点都有两个子结点，且所有叶子在同一层。

\textbf{3. 完全二叉树: }在满二叉树中，从最后一个结点开始连续去掉任意个结点后得到的二叉树。

\textbf{4. 数据操作: }前序遍历，中序遍历，后序遍历和层序遍历。

~~~~ (1) 前序遍历: 先根序遍历。遍历顺序为中-左-右。

~~~~ (2) 中序遍历: 中根序遍历。遍历顺序为左-中-右。

~~~~ (3) 后序遍历: 后根序遍历。遍历顺序为左-右-中。

~~~~ (4) 层序遍历: 从上到下的遍历层，每一层按从左到右的顺序遍历结点。

\subsection{存储结构}

\textbf{1. 顺序存储: }按层序遍历顺序，用数组存储二叉树中的所有结点。若从0开始编号，则i号结点的两个儿子为2i+1和2i+2。

\textbf{2. 二叉链表: }用一个node结构体存储单个结点，分别存储该结点的两个儿子。结构体定义如下: 

\begin{lstlisting}[language=C++]
    struct node{
        int data; 
        node *left, *right;  // 指向两个儿子结点的指针
    }; 
\end{lstlisting}

\textbf{3. 三叉链表: }在二叉链表的基础上，加一个指针指向父结点。

\subsection{算法与应用}

\textbf{1. Huffman算法: }最优二叉树构造算法

~~~~ (1) 带权路径长度: 对每个叶子结点，带权路径长度为叶子权值$\times$层数(根结点算第0层)。树的带权路径长度为所有叶子带权路径长度之和。

~~~~ (2) 最优二叉树: 给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。

~~~~ (3) Huffman算法: 贪心算法。每次将当前权值最小的两结点作为同一结点的两个儿子合并，把两个结点权值之和作为新的结点，直至只剩一个结点即根结点。

~~~~ (4) Huffman编码: 将数据出现频率作为叶子结点权重，按左0右1层序编码。显然出现频率越高的数据编码越短，且任何一个编码都不是其它编码的前缀。

\section{图}

\subsection{逻辑结构}

\textbf{1. 定义: }由顶点集合V和边集合E组成的数据结构，即G=(V,E)。

\textbf{2. 图的方向: }若顶点之间的边为有序对，则图为有向图； 若边无首尾顺序，则图为无向图。

\textbf{3. 边的权: }对边赋予的数值量，可表示距离等具体含义。

\textbf{4. 顶点的度: }以某点为顶点的边数称为该点的度。有向图中，以该点为起点的边数称为出度，以该点为终点的边数称为入度。

\textbf{5. 邻接: }若两个顶点之间存在边，则称这两个顶点邻接。

\textbf{6. 连通图: }任意两顶点间均有路径。在有向图中，任意两顶点均有路径的极大子图称为强连通分量。

\textbf{7. 数据操作: }图的遍历。分DFS和BFS两种，分别用栈和队列规划搜索顺序。

\subsection{存储结构}

\textbf{1. 邻接矩阵: }设顶点个数为n，用n * n的矩阵a存储边信息，a[i][j] 代表从i点和j点间的边权，若i点到j点无边，则a[i][j] = inf。

\textbf{2. 邻接表: }用一维数组存储顶点信息，同时挂链表存储顶点的邻接点。

\textbf{3. 三元组: }设边数为k，用 k*3 的矩阵存储边信息，三个数据分别为边权和连接的两个点。三元组适合储存点比边多得多的情形，即稀疏图。

\subsection{算法与应用}

\textbf{1. 最短路径}

~~~~ (1) Floyd算法: 多源最短路径算法，时间复杂度O($n^3$)。对任意两个点，枚举中间点以更新两点间的最短距离。

~~~~ (2) Dijkstra算法: 单源最短路径算法，时间复杂度O($n^2$)。初始化所有点为白点，从起点开始，每一轮将当前与起点距离最小的点设为蓝点，并用该点更新其它距离。

\textbf{2. 最小生成树}

~~~~ (1) Prim算法: 和Dijkstra一模一样的蓝白点算法。

~~~~ (2) Kruskal算法: 贪心算法。每次寻找当前的最短边，若不和现有边构成回路，则选用该边。

\textbf{3. 有向无环图与AOV网}

~~~~ (1) 拓扑排序: 对有向图构造拓扑序列。每次选一个没有前驱的顶点，并删去该顶点以及所有以该点为起点的边。

~~~~ (2) 关键路径: 计算活动的最早开始时间和最晚开始时间，两者相等的活动为关键活动，关键活动构成的路径为关键路径，此路径上的所有活动必须严格按期开工。

\textbf{4. 求强连通分量: }首先从某一顶点开始作DFS，得到遍历序列，再按此顺序逆向DFS，得出各强连通分量。

\section{查找技术}

\subsection{线性表的查找技术}

\textbf{1. 顺序查找: }从头到尾逐一与目标值比较。

\textbf{2. 折半查找: }在有序线性表中,每次选取区间中间值与目标比较，将搜索区域减半. 

\subsection{树表的查找技术}

\textbf{1. 二叉排序树: }一棵特殊的二叉树，左儿子小于根节点，右儿子大于根节点，且每棵子树均是二叉排序树。

\textbf{2. 平衡二叉树: }左右子树的深度至多相差1。将二叉排序树的不平衡点调整为平衡二叉树，能优化平均查找效率。

\textbf{3. B树: }一棵特殊的m叉树，根结点至少有2棵子树，其它结点至少有m/2棵，所有叶子结点出现在同一层。

\subsection{散列表的查找技术}

\textbf{1. 基本思想: }构建数据到关键码的映射，根据关键码定位数据。

\textbf{2. 散列函数设计: }通常使用除留余数法，选定适当的素数p，用数据模p的余数作为关键码。

\textbf{3. 处理冲突的方法: }开放定址法，即在冲突位置的下一个空地址处存储； 挂链表法，即散列表存储每个同义词链表的头指针，遇到冲突就把数据挂到对应链表尾部。

\section{排序技术}

\subsection{插入型排序}

\textbf{1. 直接插入排序: }对每一个元素，在已排序序列中找到合适的位置并插入。

\textbf{2. 希尔排序: }将整个序列分为若干子序列执行插入排序，最后对所有子序列执行插入排序。

\subsection{交换型排序}

\textbf{1. 冒泡排序: }两两比较相邻记录，若顺序不对则交换。

\textbf{2. 快速排序: }将序列对半分，在左右区间中选择顺序不对的两个元素交换。

\subsection{选择型排序}

\textbf{1. 选择排序: }从未排序序列中依次选择最大/最小值，组成有序序列。

\textbf{2. 堆排序: }维护一个大根堆，每次将堆顶元素作为最大值导出。

\subsection{归并型排序}

\textbf{1. 二路归并: }将序列划分为两个序列，分别排序后合并为有序序列。

